In a Local Area Network (LAN) of computing nodes, connections are formed via switches and links. It is desirable that frames take the shortest route—traversing the fewest number of switches and links—from one node to another. It is also desirable to create a redundant system in which there is an alternative communication path in the event of failure of any switch or link.
A Virtual LAN (VLAN) is a method of creating several independent LANs that share the same set of links, i.e. physical wires. Frames are marked by the sender so that the receiver knows which VLAN the frame belongs to. A VLAN may incorporate a subset of all the links in a LAN for the purpose of restricting traffic to a certain set of nodes in the LAN. VLANs also serve to provide alternative paths should some switches or links become unavailable.
Ethernet is a well known standard LAN technology. In an Ethernet LAN, every node has a unique address. Frames are sent from one node to another by directly addressing the destination node. Each frame also contains the source address (analogous to a postal return address). Frames may also be broadcast, meaning all nodes on the LAN receive them. Ethernet switches learn about nodes by observing the source addresses of frames received by the switches, after which frames addressed to a learned address can be delivered.
Ethernet supports VLANs with a standard way of tagging frames. A tag is also known as a VLAN Identifier (VID). A link carrying VLAN tagged frames is known as a trunk link.
The desire for redundancy and bandwidth leads to creating a network with multiple possible paths for a frame to get from one node to another. However, there must not be loops (cycles) in the network topology or broadcast frames would be replicated and cycled indefinitely. The well known spanning tree protocol was developed for Ethernet LANs to ensure that no such cycles exist by disabling redundant links.
A spanning tree is a computer science notion. It is a tree that includes all nodes of a graph. In other words, it is a connectivity scheme that has only one possible path from any one node to any other. A Spanning Tree Protocol, (STP) as defined in IEEE802.1D is a protocol for determining the spanning tree for the nodes of an Ethernet network. STP restricts the topology of the network so that the path from the “root” to any other node traverses the least possible number of nodes. A Multiple Spanning Tree (MST) is defined in IEEE802.1Q-(2003 edition). Each MST provides a set of unique spanning trees which each define a specific path between each pair of nodes, each one of which is referred to as a Multiple Spanning Tree Instance (MSTI) Any number of VLANs can be assigned to each MSTI of a spanning tree. Within any MSTI the shortest path exists from the root node to any other node.
MST configuration is difficult and error prone, as the same information must be configured on each switch in the LAN or else the scheme will fall back to rapid spanning tree (RST, 802.1D-2004) or simply spanning tree (802.1d).
Thus there is need for an automated mechanism to maximize link utilization other than typical routing and switching with arbitrary spanning tree behavior.